#include"tree.h"
#include<stdlib.h>
#include"sqstack.h"
#include<unistd.h>

void Init(BinaryTree * bt,char ref)
{
	bt->root = NULL;
	bt->refvalue = ref;
}
void Create(BinaryTree *bt)
{
	printf("请输入结点顺序:");
	Create_(bt,&bt->root);
}
void Create_(BinaryTree *bt, BinaryTreeNode **root)
{
	char item;
	scanf("%c", &item); //输入：ABC##DE##F##G#H##
	if (item == bt->refvalue)
		*root = NULL;
	else
	{
		BinaryTreeNode *node;
		node = malloc(sizeof(BinaryTreeNode));
		if (node == NULL)
			exit(1);
		node->data = item;
		*root = node;//修改变量的值,函数参数为一级指针;修改指针的值,函数参数为二级指针
		Create_(bt, &(*root)->leftchild);
		Create_(bt, &(*root)->rightchild);
	}
}

void Create4(BinaryTree * bt,char ** str)
{
	Create4_(bt,&bt->root,str);
}
void Create4_(BinaryTree * bt,BinaryTreeNode ** root,char ** str)
{
	if(**str == bt->refvalue)
		*root = NULL;
	else
	{
		*root = malloc(sizeof(BinaryTreeNode));
		if(*root == NULL)
			exit(1);
		(*root)->data = **str;
		//************重要操作***************
		//递归保存的变量的值不会更新，导致在B的右孩子处，字符串指针指向的位置还是字符C
		//而在处理C结点后字符串指针是指向D，按照执行创建操作时程序在运行时所有保存的递归过程的字符串指针指向的位置应该相同,所以这时就要函数传参二级指针，每次修改字符串的起始位置。
		++(*str);    //修改字符串的初始位置
		Create4_(bt, &(*root)->leftchild, str);
		++(*str);
		Create4_(bt, &(*root)->rightchild, str);
	}
}

void Create_VLR_LVR(BinaryTreeNode ** node,char * VLR,char * LVR,int n)
{
	BinaryTreeNode *current;

	if (n == 0)
		*node = NULL;
	else
	{
		int k = 0;
		while (LVR[k] != VLR[0])
			k++;
		current = malloc(sizeof(BinaryTreeNode));
		if (current == NULL)
		{
			perror("malloc()");
			exit(EXIT_FAILURE);
		}
		current->data = LVR[k];
		*node = current;
		Create_VLR_LVR(&current->leftchild, VLR + 1, LVR, k); //左子树个数刚好为k,左子树的结点出现在LVR中前k个结点
		//右子树结点出现在LVR中依据VLR和LVR找到的根的右边结点,个数为n-k-1
		Create_VLR_LVR(&current->rightchild, VLR + k + 1, LVR + k + 1, n - k - 1);
	}
}

void Create_LVR_LRV(BinaryTreeNode ** node,char * LVR,char * LRV,int n)
{
	BinaryTreeNode * current;
	if(n == 0)
		*node = NULL;
	else
	{
		int k = 0;
		while(LVR[k] != LRV[n-1])
			k++;
		current = malloc(sizeof(BinaryTreeNode));
		if(current == NULL)
		{
			perror("malloc()");
			exit(EXIT_FAILURE);
		}
		current->data = LVR[k];
		*node = current;

		Create_LVR_LRV(&current->leftchild, LVR, LRV, k);
		Create_LVR_LRV(&current->rightchild, LVR + k + 1, LRV + k, n - k - 1);
	}
}

void PreOrder(BinaryTree * tree)
{
	PreOrder_(tree->root);
	printf("\n");
}
void PreOrder_(BinaryTreeNode * root)
{
	if(root != NULL)
	{
		printf("%c",root->data);
		PreOrder_(root->leftchild);
		PreOrder_(root->rightchild);
	}
}

void InOrder(BinaryTree * tree)
{
	InOrder_(tree->root);
	printf("\n");
}
void InOrder_(BinaryTreeNode * root)
{
	if(root != NULL)
	{
		InOrder_(root->leftchild);
		printf("%c",root->data);
		InOrder_(root->rightchild);
	}
}

void PostOrder(BinaryTree * tree)
{
	PostOrder_(tree->root);
	printf("\n");
}

void PostOrder_(BinaryTreeNode * root)
{
	if(root != NULL)
	{
		PostOrder_(root->leftchild);
		PostOrder_(root->rightchild);
		printf("%c",root->data);
	}
}

int Size(BinaryTree * tree) //求二叉树的结点个数
{
	return Size_(tree->root);
}

int Size_(BinaryTreeNode *node)
{
	if(node == NULL)
		return 0;
	return Size_(node->leftchild) + Size_(node->rightchild) + 1;
}

int Height(BinaryTreeNode * node)       //求二叉树的高度
{
	if(node == NULL)
		return 0;
	int left_height = Height(node->leftchild);
	int right_height = Height(node->rightchild);
	return (left_height > right_height ? left_height : right_height) + 1;
}

BinaryTreeNode * Search(BinaryTreeNode * node,char key)
{
	if(node == NULL)	
		return NULL;
	//printf("%c  ",node->data);     //显示递归执行顺序
	if(node->data == key)
		return node;
	BinaryTreeNode * p = Search(node->leftchild,key);   //在左树中寻找
	if(p != NULL)
		return p;       //关键，左树中找到就直接返回,不需要再查找
	return Search(node->rightchild,key);
}

BinaryTreeNode * Parent(BinaryTreeNode * p,BinaryTreeNode * node)
{
	if(p == NULL || node == NULL)
		return NULL;             //这两种情况都不可能有父节点 
	if(p->leftchild == node || p->rightchild == node)
		return p;
	BinaryTreeNode *q = Parent(p->leftchild,node);
	if(q != NULL)
		return q;
	return Parent(p->rightchild,node);
	printf("%d\n",__LINE__);
}

BinaryTreeNode * LeftChild(BinaryTreeNode *p)
{
	return p->leftchild;
}

BinaryTreeNode * RightChild(BinaryTreeNode *p)
{
	return p->rightchild;
}

int Empty(BinaryTree * tree)
{
	return tree->root == NULL;
}

void Copy(BinaryTreeNode * p, BinaryTreeNode ** q)     //拷贝一棵树
{
	if(p == NULL)
		*q = NULL;
	else
	{
		*q = malloc(sizeof(BinaryTreeNode));
		if(*q == NULL)
			exit(1);
		(*q)->data = p->data;
		Copy(p->leftchild,&(*q)->leftchild);
		Copy(p->rightchild,&(*q)->rightchild);
	}

	//把Copy函数写在外面的写法,这时如果p为空则不能取leftchild，所以在p为空时需直接返回
	//if (p == NULL)
	//{
	//	*q == NULL;
	//	return;
	//}
	//else
	//{
	//	*q = malloc(sizeof(BinaryTreeNode));
	//	if (*q == NULL)
	//		exit(1);
	//	(*q)->data = p->data;
	//}
	//Copy(p->leftchild, &(*q)->leftchild);
	//Copy(p->rightchild, &(*q)->rightchild);
}
void Clear(BinaryTreeNode ** node)
{
	BinaryTreeNode * current = *node;
	if(current != NULL)
	{
		Clear(&current->leftchild);
		Clear(&current->leftchild);
		free(current);
		*node = NULL;
		//current = NULL;     错误写法
	}

}
//void _PreOrder(BinaryTreeNode *node)
//{
//	sqstack *stack;
//	stack = stack_create();
//	stack_push(stack,node);
//	BinaryTreeNode *current;
//	while (!stack_isempty(stack))
//	{
//		stack_pop(stack,current);      //栈顶元素出栈
//		printf("%c", current->data);
//		if (current->rightchild != NULL)
//			stack_push(stack,current->rightchild);  //右孩子入栈
//		if (current->leftchild != NULL)
//			stack_push(stack,current->leftchild); //左孩子入栈
//	}
//	printf("\n");
//}
//void _InOrder(BinaryTreeNode *node)
//{
//	BinaryTreeNode * current;
//	sqstack *stack;
//	stack = stack_create();
//	if (node != NULL)
//	{
//		stack_push(stack, node);
//		while (!stack_isempty(stack))   //循环条件：栈非空
//		{
//			while (node->leftchild != NULL) //一直向左，直到左子树为空
//			{
//				stack_push(stack, node->leftchild);
//				node = node->leftchild;
//			}
//			stack_pop(stack, current); //左子树为空，结点出栈
//			printf("%c", current->data);
//			if (current->rightchild != NULL) //结点的右子树不为空，将右子树作为根访问
//			{
//				node = current->rightchild;
//				stack_push(stack, node);
//			}
//		}
//	}
//	printf("\n");
//}

#if 1
int _PostOrder(BinaryTreeNode *node)
{
	if (node == NULL)
		return -1;

	sqstack *stack;
	BinaryTreeNode *current;
	stkNode sn;
	int flag;

	stack = stack_create();

	do
	{
		while (node != NULL)
		{
			sn.ptr = node;
			sn.tag = L;
			stack_push(stack, &sn);
			node = node->leftchild;
		}
		stack_pop(stack, &sn);
		current = sn.ptr;
		switch (sn.tag)
		{
		case R: //标记为右,表示右子树已访问,直接访问根结点
			current = sn.ptr;
			printf("%c ", current->data);
			break;
		case L:		    //标记为左,还要访问右节点
			sn.tag = R; //修改标记为右
			stack_push(stack, &sn);
			node = current->rightchild;
			break;
		}
	} while (!stack_isempty(stack));

	printf("\n");
	return 0;
}
#endif